#include <string.h>
#include <stdlib.h>

//KMP用于寻找某字符串中是否包含某一字串问题

//求得KMP中的next数组，next数组用于记录对应位字符前的最大
//前缀和后者子串匹配长度，例如abbabbw，则w对应next数组的值为3
//计算该值可以根据该字符前一个字符的next数组值得到
int* GetNextArr(const char* str)
{
    int len = strlen(str);
    int *nextArr = (int *)malloc(sizeof(int) * len);
    //初始化next[0] = -1, next[1] = 0
    nextArr[0] = -1;
    if(len < 2)
        return nextArr;
    nextArr[1] = 0;
    //从2位置开始，需与next[1]比较，所以cn = next[1] = 0
    int i = 2, cn = 0;
    while(i < len)
    {
        if(str[i - 1] == str[cn])
            nextArr[i++] = ++cn;
        else if(cn > 0)
            cn = nextArr[cn];
        else
            nextArr[i++] = 0;
    }
    return nextArr;
}

// 从字符串strParent中找到子串strChild
// 如有，返回最早出现位置；否则返回-1
int KMP(const char *strParent, const char *strChild)
{
    int *next = GetNextArr(strChild);
    int p_cur = 0, c_cur = 0;
    int p_len = strlen(strParent), c_len = strlen(strChild);
    while(p_cur < p_len && c_cur < c_len)
    {
        if(strParent[p_cur] == strChild[c_cur])
        {
            ++p_cur;
            ++c_cur;
        }
        else if(c_cur > 0)
        {
            c_cur = next[c_cur];
        }
        else
        {
            ++p_cur;
        }
    }
    return c_cur == c_len ? p_cur - c_len : -1;
}
